//https://leetcode.cn/problems/find-a-peak-element-ii/submissions/489926102/?envType=daily-question&envId=2023-12-19



class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int midx = m / 2, midy = n / 2; 
        vector<int> ans(2);
        while (1) {
            int num = mat[midx][midy], mai = midx, may = midy;
            int left = midx > 0 ? mat[midx - 1][midy] : -1;
            int right = midx < m - 1 ? mat[midx + 1][midy] : -1;
            int up = midy > 0 ? mat[midx][midy - 1] : -1;
            int down = midy < n - 1 ? mat[midx][midy + 1] : 1;
            if (left < num && right < num && up < num && down < num) {
                ans[0] = mai;
                ans[1] = may;
                break;
            } else {
                if (right > num) {
                    mai = midx + 1;
                    num = right;
                }
                if (left > num) {
                    mai = midx - 1;
                    num = left;
                }
                if (up > num) {
                    may = midy - 1;
                    mai = midx;
                    num = up;
                }
                if (down > num) {
                    may = midy + 1;
                    mai = midx;
                    num = down;
                }
                midx = mai;
                midy = may;
            }
        }
        return ans;
    }
};